package com.demo.jzoffer2;

import org.junit.Test;

import java.util.Stack;

/**
 * @author gy
 * @date 2022/11/15
 */
public class Test1228_01 {

    /**
     * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，
     * 调用 min、push 及 pop 的时间复杂度都是 O(1)。
     *
     * MinStack minStack = new MinStack();
     * minStack.push(-2);
     * minStack.push(0);
     * minStack.push(-3);
     * minStack.min();   --> 返回 -3.
     * minStack.pop();
     * minStack.top();      --> 返回 0.
     * minStack.min();   --> 返回 -2.
     *
     * 各函数的调用总次数不超过 20000 次
     */
    class MinStack {

        /** initialize your data structure here. */
        Stack<Integer> A,B;
        public MinStack() {
             A = new Stack<>();
             B = new Stack<>();
        }

        public void push(int x) {
            A.add(x);
            // 辅助栈B为空，或者 B栈的栈顶值 >= 压入的值x 时，才入栈；
            // 此操作可以保证 B栈 从栈底 —> 栈顶 非严格降序；栈顶元素为min值
            // = 代表重复元素
            if (B.isEmpty() || B.peek() >= x){
                B.add(x);
            }
        }

        public void pop() {
            // 需要特别注意：此时A.pop() 已经执行
            // Removes the object at the top of this stack and returns that
            //     * object as the value of this function.
            if (A.pop().equals(B.peek())){
                B.pop();
            }
        }

        public int top() {
            return A.peek();
        }

        public int min() {
            // B栈的栈顶元素始终为最小值
            return B.peek();
        }
    }

    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.min();
     */


    @Test
    public void m1() {

    }

}
